Longest palindrome

Time: O(N); Space: O(1); easy

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:

  • Assume the length of given string will not exceed 1,010.

Example 1:

Input: s = “abccccdd”

Output: 7

Explanation:

  • One longest palindrome that can be built is “dccaccd”, whose length is 7.

1. Greedy [O(N), O(1)]

Intuition

A palindrome consists of letters with equal partners, plus possibly a unique center (without a partner). The letter i from the left has its partner i from the right. For example in ‘abcba’, ‘aa’ and ‘bb’ are partners, and ‘c’ is a unique center.

Imagine we built our palindrome. It consists of as many partnered letters as possible, plus a unique center if possible. This motivates a greedy approach.

Algorithm

For each letter, say it occurs v times. We know we have v // 2 * 2 letters that can be partnered for sure. For example, if we have ‘aaaaa’, then we could have ‘aaaa’ partnered, which is 5 // 2 * 2 = 4 letters partnered.

At the end, if there was any v % 2 == 1, then that letter could have been a unique center. Otherwise, every letter was partnered. To perform this check, we will check for v % 2 == 1 and ans % 2 == 0, the latter meaning we haven’t yet added a unique center to the answer.

[7]:

import collections

class Solution1(object):
    """
    Time: O(N), where N is the length of s. We need to count each letter.
    Space: O(1), the space for our count, as the alphabet size of s is fixed.
           We should also consider that in a bit complexity model,
           technically we need O(LogN) bits to store the count values.
    """
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        for v in collections.Counter(s).values():
            ans += v // 2 * 2
            if ans % 2 == 0 and v % 2 == 1:
                ans += 1
        return ans

[8]:

sol = Solution1()
s = "abccccdd"
assert sol.longestPalindrome(s) == 7

2. [O(N), O(1)]

[9]:

import collections

class Solution2(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        odds = 0
        for k, v in collections.Counter(s).items():
            odds += v & 1

        return len(s) - odds + int(odds > 0)

[11]:

s = Solution2()
s = "abccccdd"
assert sol.longestPalindrome(s) == 7

[12]:

import collections

class Solution3(object):

    def longestPalindrome2(self, s):
        """
        :type s: str
        :rtype: int
        """
        odds = sum(map(lambda x: x & 1, collections.Counter(s).values()))

        return len(s) - odds + int(odds > 0)

[13]:

s = Solution3()
s = "abccccdd"
assert sol.longestPalindrome(s) == 7